package Demo03;

import java.math.BigInteger;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) {
        int[] a = new int[9];
        BigInteger b = BigInteger.valueOf(0);
        BigInteger i = BigInteger.valueOf(0);
/*        for (long j = 0; j < 202320232023; j++) {
        }*/
    }
    public static void main3(String[] args) {
        /*int[] d = {1, 4, 6, 7, 8, 20};
        int[] c = {2, 7, 15};
        System.out.println(mincostTickets(d, c));*/
//        int[][] a = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};
        int[][] a = {{1, 0, 0}, {0, 0, 0}, {0, 0, 0}};

        System.out.println(maxDistance(a));
    }


    public static int maxDistance(int[][] grid) {
        //宽
        int m = grid.length;
        //长
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    //0代表海洋
                } else {
                    //陆地
                    //放入队列
                    queue.add(new int[]{i, j});
                    //                  0  1
                }
            }
        }
        if (queue.isEmpty() || queue.size() == m * n) {
            return -1;
        }
        int last = -1;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            //纵坐标
            int i = tmp[0];
            //横坐标
            int j = tmp[1];
            //距离
            last = grid[i][j] + 1;
            if (i - 1 >= 0 && grid[i - 1][j] == 0) {
                //左
                grid[i - 1][j] = last;
                queue.add(new int[]{i - 1, j});
            }
            if (j - 1 >= 0 && grid[i][j - 1] == 0) {
                //上
                grid[i][j - 1] = last;
                queue.add(new int[]{i, j - 1});

            }
            if (i + 1 <= m - 1 && grid[i + 1][j] == 0) {
                //下
                grid[i + 1][j] = last;
                queue.add(new int[]{i + 1, j});

            }
            if (j + 1 <= n - 1 && grid[i][j + 1] == 0) {
                //右
                grid[i][j + 1] = last;
                queue.add(new int[]{i, j + 1});

            }
        }

        return last - 2;
    }

    private static int[] time = {1, 7, 30};

    public static int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        return minCost(days, costs, 0, dp);
    }

    private static int minCost(int[] days, int[] costs, int i, int[] dp) {
        if (i == days.length) {
            return 0;
        }
        if (dp[i] != Integer.MAX_VALUE) {
            return dp[i];
        }
        int j = i;
        int ans = Integer.MAX_VALUE;
        for (int k = 0; k < 3; k++) {
            while (j < days.length && days[i] + time[k] > days[j]) {
                j++;
            }
            ans = Math.min(ans, minCost(days, costs, j, dp) + costs[k]);
        }
        dp[i] = ans;
        return ans;
    }

    public static void main1(String[] args) {
        int[] arr = {7, 2, 5, 10, 8};
        System.out.println(splitArray(arr, 2));
    }

    public static int splitArray(int[] nums, int k) {
        int l = 0;
        int r = 0;
        for (int num : nums) {
            r += num;
        }
        // 总和范围: l ~ r
        int ans = 0;
        int m = 0;
        while (l <= r) {
            // 中点
            // 检查中点是否是最后的值
            m = l + ((r - l) >> 1);
            // m放入f函数, 至少得到n个组
            int n = f(m, nums);
            // 如果n的个数小于k, 这样设计的每组都较之前大
            // 不符合条件, 调小一点
            if (n <= k) {
                r = m - 1;
                ans = m;
            } else {
                // n的个数大于k, 每组的最大值较小
                l = m + 1;
            }
        }

        return ans;
    }

    private static int f(int m, int[] nums) {
        int num = 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 如果大于m的话,就说明这个数太小了,需要扩大
            if (nums[i] > m) {
                return Integer.MAX_VALUE;
            }
            if (sum + nums[i] <= m) {
                sum += nums[i];
            } else {
                sum = nums[i];
                num++;
            }
        }
        return num;
    }
}


